CODE 145. Sort List

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/26/2013-11-26-CODE 145 Sort List/

访问原文「CODE 145. Sort List」

Sort a linked list in O(n log n)
time using constant space complexity.

public ListNode sortList(ListNode head) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	ArrayList<Integer> its = new ArrayList<Integer>();
	ListNode tmp = head;
	while (null != tmp) {
		its.add(tmp.val);
		tmp = tmp.next;
	}
	int[] is = new int[its.size()];
	for (int i = 0; i < its.size(); i++) {
		is[i] = its.get(i);
	}
	Arrays.sort(is);
	tmp = head;
	for (int i = 0; i < its.size(); i++) {
		tmp.val = is[i];
		tmp = tmp.next;
	}
	return head;
}